//990.等式方程的可满足性
//https://leetcode.cn/problems/satisfiability-of-equality-equations/
class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        int n = equations.size();
        vector<int> ufs(26,-1);

        function<int(int)> FindRoot = [&ufs](int s) {
            while(ufs[s] >= 0) s = ufs[s];
            return s;
        };

       //将=关系添加到集合中
       for(int i = 0;i<n;++i)
        {
            if(equations[i][1] == '=')
            {
                int root1 = FindRoot(equations[i][0]-'a');
                int root2 = FindRoot(equations[i][3]-'a');
                if(root1 == root2) continue;

                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        }
        //如果两元素关系为!= 但是两元素在集合中 这是不符合要求的
        for(int i = 0;i<n;++i)
        {
            if(equations[i][1] == '!')
            {
                int root1 = FindRoot(equations[i][0]-'a');
                int root2 = FindRoot(equations[i][3]-'a');
                if(root1 == root2) return false;
            }
        }

        return true;

    }
};